Image matching is one of the core techniques in the computer vision and image processing domains, of which wide applications are found in 3-D reconstruction, image stitching, and object recognition. Particularly, in the context of 3-D reconstruction of large-scale scenes, due to the time consuming in the process of the large-scale image matching, 3-D reconstruction often suffers from the low processing speed. Therefore, it is urgent to resolve the fast and accurate image matching issue.
Image matching techniques can be roughly categorized into three groups: point matching, line matching, and region matching. Due to its robustness to illumination variations, affine transformation, and view-angle changes, point matching is mostly concerned and many effective algorithms have been proposed. Nevertheless, point matching can be very time-consuming: the time complexity of point matching between two images is O(N2), where N is the average number of key-points in each image. For the brute-force matching method, the key-point matching problem can be regarded as a nearest neighbor search problem. As an alternative, approximate nearest neighbor search is proposed, e.g. the famous tree-based key-point matching algorithm. In this algorithm, data are efficiently stored in a tree-like structure to speed-up the search process. Yet, all tree-based methods tend to be much less efficient when dealing with high-dimensional data, and may even be inferior to the simple linear scan.